package leetcode.D200.T138;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: duyuzhou
 * @Create: 2022-04-07 23:18:02 星期四
 */

class Solution {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    // 解法一:哈希,空间复杂度为O(n)
    /*public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node dummy = new Node(0), p = dummy, q = head;
        while (q != null) {
            p.next = new Node(q.val);
            p = p.next;
            map.put(q, p);
            q = q.next;
        }
        p = dummy.next;
        q = head;
        while (p != null) {
            p.random = map.get(q.random);
            p = p.next;
            q = q.next;
        }
        return dummy.next;
    }*/

    // 解法二:原理
    public Node copyRandomList(Node head) {
        Node p = head;
        while (p != null) {
            Node temp = new Node(p.val);
            temp.next = p.next;
            p.next = temp;
            p = temp.next;
        }
        p = head;
        while (p != null) {
            if (p.random != null)
                p.next.random = p.random.next;
            p = p.next.next;
        }
        if (head == null)
            return null;
        p = head;
        Node tHead = head.next, q = tHead;
        while (p != null) {
            p.next = q.next;
            p = p.next;
            if (p == null) {
                break;
            }
            q.next = p.next;
            q = q.next;
        }
        return tHead;
    }
}
